ATM switches need to provide a path between an input channel connected to the source point and an output channel connected to the destination point with a very high probability of successful transmission. The class of ATM switches satisfying such a requirement is called point-to-point switches (or single-channel switches as opposed to multi-channel switches). As shown in the prior art, point-to-point switches can be classified in terms of switching method, resulting in shared memory switches, shared median switches, and space division switches.
Even in an internally nonblocking point-to-point switch, throughput can be severely limited by other factors such as output contention and head of line blocking. As a result, a variety of buffering methods have been suggested, which leads to another way of classifying switches into internal buffer, input buffer, output buffer, and shared buffer.
Multicasting has been identified as an essential function in broadband communication networks, and examples of such are reported in the prior art.
An important issue for ATM is the development of a switching methodology that can support the very high bandwidth transmission associated with lightwave technology. The transmission rate over optical fibers has reached tens of gigabits per second and is likely to increase in the coming years. On the other hand, the processing speed of electronic switches remains substantially slower. Such a mismatch between the two quantities creates a natural bottleneck at the switching nodes in the network. A number of strategies have been proposed in the literature to improve the speed of packet switches and comprehensive surveys of these appear in the prior art.
Multi-channel switches have been proposed and studied in the literature as a means of alleviating the processing speed constraint of electronic switches in broadband networks. Multi-channel switches can provide higher performance (e.g., throughput, cell loss probability, delay) by exploiting the concept of channel grouping. Instead of being routed to a specific output channel, a packet is routed to any channel belonging to an appropriate channel group. (In the literature, channel group is also referred to as trunk group.) In ATM, a session is established by the assignment of a virtual circuit. The virtual circuit is defined in terms of a set of channels in transmission links connecting between the two end points of the session. However, many of the benefits associated with connection-oriented services do not require that the connection be specified at the channel level; it is sufficient to specify the path of the connection, not the specific channel within the path. This implies, among other things, that a packet can be routed to any one of a group of channels that connect the same two end points. We note that any interswitch connection is likely to be in the range of multiple gigabits per second, e.g., 2.4 gigabits per second via an 0C48 connection of SONET. This corresponds to a number of ATM channels at 155 or 620 megabits per second, and a channel group may be defined as a collection of these channels transmitted over a single optical fiber.
The concept of channel grouping has been exploited for point-to-point channel switches. Path trunking has been considered as a means of reducing cell loss probability. Trunk grouping has been implemented to resolve output contention. The main purpose of channel grouping has been to provide higher throughput. Also, a link group has been used, but it differs from the channel grouping concept in that no statistical multiplexing is achieved in a link group.
One of the first reported architectures with multi-channel capability is found in Pattavina, A., "multi-channel Bandwidth Allocation in a Broadband Packet Switch," IEEE Journal of Selected Areas in Communications, Volume 6, No. 9, December, 1988, pp. 33-38. The switch proposed in Pattavina is internally nonblocking and is based on the Batcher-Banyan network. It requires O((log.sub.2 N).sup.2) stages of interconnected 2.times.2 switching elements and it employs an input buffering scheme to resolve the output contentions, which requires a complex, three phase algorithm to allocate bandwidth. Lau, P. S. and Leon-Garcia, A., "Design and Analysis of a Multi-link Access Subsystems Based on the Batcher-Banyan Network Architecture," IEEE Trans. Commun., vol. 40, No. 11, November 1992, pp. 1757-1766 improves upon Pattavina in the bandwidth allocation complexity, however the improvement is slight. The input buffering schemes used in Lau and Pattavina do not achieve the optimal delay-throughput performance.
On the other hand, others use deflection routing in an Omega network of log.sub.2 N stages, but they result in non-zero blocking probability. To achieve a reasonable cell loss probability (e.g., 10.sup.-6), the switch utilization must be kept low. These networks are self-routing networks which require minimal complexity in call set-up control. The output of the switch is partitioned into channel groups as a function of the input probability; it implies that as the utilization of the switch changes, it is necessary to modify the partition to maintain the performance level, which is clearly undesired.
As the demand for new applications soars, greater variability in bandwidth and traffic characteristics (e.g., session duration, burstiness) is expected. The advantages of statistically sharing a higher channel capacity under such conditions are well known. For example, the link efficiency is increased by reducing the burstiness in the incoming traffic. Bit pipes of higher rates are formed which allow a number of applications to share bandwidth by dynamically allocating time slots. Assuming that the exogenous traffic intensity is fixed, a larger channel group size is less likely to incur blocking for a single ATM cell, for a burst of cells, or for a new connection request. Similarly, other performance measures such as delay, buffer overflow, and congestion would improve when multiple channels are grouped together as a single resource.
Another important benefit of multi-channel switching is the ability to provide super-rate switching. Applications requiring peak rates greater than a single ATM channel capacity would suffer high cell loss probability unless these applications can be assigned over multiple channels. Channel grouping would be a natural way to deal with such a problem. In reality, a channel group may correspond to a single fiber operating at an extremely high rate, and multi-channel switches can provide a means of transporting this bit pipe across broadband networks.
To solve these and other problems in the prior art, the inventors have succeeded in developing a switching paradigm that efficiently accomplishes multi-channel switching as a generalization of point-to-point switching paradigms that are currently prevalent. The resulting architecture must maintain the required features of point-to-point switching while providing the advantages of multi-channel switching as mentioned earlier. The required features of the switching architecture may be summarized as follows:
Multi-Channel Switching. The switch provides the ability to define output channels as a channel group; the output is partitioned into a number of channel groups with arbitrary cardinality. This ensures that the switch can support super-rate (i.e., rate that exceeds capacity of a single channel) switching of arbitrary bandwidth. Partition must be flexible and should not burden the switch with additional hardware and control complexities. PA1 In-Order Cell Sequencing. One important benefit of a connection-oriented protocol is that the ordering among the cells belonging to a single session is maintained. In multi-channel switching, since cells belonging to a session can traverse over multiple channels, and thus they can experience a widely differing amount of delay and congestion, maintaining the ordering among them becomes a challenging issue. We aim to develop an architecture that guarantees in-order cell sequencing. Thus the need for a re-sequencing mechanism, which is often complex and expensive to implement, is eliminated. This issue has not been addressed by any previous work on multi-channel switching known to the inventors. PA1 Simplicity. The multi-channel switching should be facilitated without necessarily increasing the complexity of the switch; this includes hardware complexity such as connection set up, flow control, and address translation. Observing the fact that the routing constraint in a multi-channel switch, where cells only need to arrive at any one of a number of output channels in the same channel group, is less stringent than point-to-point switching, it should be possible to reduce the switching complexity. The switch must be scalable to a large number of input and output channels (e.g., 2.sup.16). PA1 High Performance. To ensure high performance, we constrain the internal fabric of the switch to be nonblocking and bufferless. A switch is non-blocking if every permutation of inputs which does not cause output conflicts can be realized by the switch. A bufferless architecture implies that at each switching element, all input cells must be transferred to the output without delay. These two constraints assure higher throughput and lower delay. PA1 Multicasting. The ability to support multicast connections is considered an essential function for broadband networks. For example, broadcast video, teleconferencing and LAN bridging are services that require multicast capability. When cells are duplicated for multicasting, it is important to ensure that the ordering among the duplicated cells is maintained; such a requirement is not addressed in the previous multicasting architectures shown in the prior art. The issue of multicasting has not been discussed in the previous multi-channel switching works. PA1 Multi-Rate Switching. It is desired that a single switch supports bit pipes of different bandwidths. For example, the current ATM standard defines two rates, viz., 155 and 620 megabits per second. Since the switch of the present invention allows channel group sizes to be defined arbitrarily, the two rates can be simultaneously supported in a single switch which corresponds to the capability of multi-rate switching. PA1 Multiple Performance Requirements. As services with differing performance requirements are integrated into an ATM network, it is necessary to accommodate the characteristics of individual services as part of the managing capacity of the network. For example, consider two classes of service wherein one requires a tight bound on delay jitter with less stringent cell loss probability (e.g., voice and real-time video), and the other requires a small cell loss probability with more tolerance towards delay (e.g., file transfer). It is important to perform switching according to the differing performance requirements, especially when the network is congested by heavy traffic. In the switch architecture of the present invention, the aforementioned two classes of service may be accommodated, with a moderate amount of increase in the switching complexity. PA1 Fairness. Sessions established at different input channels may not experience the same performance. Similarly, different output destinations may suffer from discriminating delay or throughput levels. Some switch architectures address this issue by specific provisions of fairness. In the switch of the present invention, fairness may be ensured at the cost of a relatively minor increase in switching complexity.
The inventors achieve the foregoing advantages while using a building block approach to constructing the switch. At its core is an NBGN or nonblocking binary group network which is itself comprised of a running adder and a Flip Network. An NBGN is a functional block that separates two groups of cells in a manner that cells belonging to the same group appear at the output as compact modulo N (N=number of inputs). The connection patterns in the NBGN are assigned such that the separation into any number of channel groups is achieved with minimal hardware functions and at the same time, the relative ordering among the cells is maintained. These NBGN's may be cascaded or data cells may be recycled through the NBGN as the inventors implement a bufferless switch. This recursive use of a single NBGN minimizes hardware to do multiple sorts of data cells into groups as required to separate them for transmission over multiple channel groups connected to the output of the switch to thereby achieve multi-channel switching.
For those applications requiring a large number of channel groups, such as might be experienced in a network with a large number of switches which are highly interconnected, an NBGN with a number of inputs equal to CN, where C is some positive integer and N is the number of input channels, reduces the speed constraint on the recursive use of the NBGN required by a large number of channel groups.
The inventors herein also take this multi-channel switch and expand it to accommodate multicasting using the same NBGN "building block" architecture. In essence, the multicasting/multi-channel switch of this invention includes a multicasting phase and a routing phase, and the inventors propose variations thereon to minimize memory requirements which might otherwise defeat this implementation.
The inventors also demonstrate how use of a recursive NBGN, or RNBGN, in the multicasting phase permits the data cells to be grouped according to a class of service to thereby provide priority of data cell transfer to be higher in one class than in another. This implementation facilitates the additional charges for value added service which are highly desirable in telecommunication networks.
One of the distinguishing features of the inventors' implementation in this multicasting/multi-channel architecture is the use of a Gray code numbering for labeling the cells for sorting. This Gray code ordering simplifies the hardware requirements to sort the data cells and is an elegant implementation which facilitates the class of service and fairness requirements. Still another distinguishing feature of the present invention is its ability to maintain the data cells in time order depending upon their relative position amongst the inputs within the same time period. By maintaining this relative position of the data cells as the data cells are processed, which may include recycling, the data cells remain in strict time sequence and thus the inventors eliminate the requirement of a resequencer as is commonly implemented in many prior art switches.
Eliminating the need for a resequencer along with the performance and control complexity gain in the present architecture facilitates the switch's use in switching data streams which more closely approach the data transmission capacities of fiber optic and other high speed channels to thereby minimize the bottleneck effect created by prior art switching architectures. As explained above, this consideration is very important in the future implementation of high speed data links as the limits of data speed transfer rates continue to be pushed.